#选择排序
def SelectionSort(a):
    n = len(a)
    for i in range(n-1):
        min = i
        for j in range(i+1,n):
            if (a[j] > a[min]):
                min = j
    #从i到n-1的数字中，找到一个值最小的数的下标存到min的变量里
        a[i], a[min] = a[min], a[i] #第i个数和刚找出来最小元素进行位置交换
        print(a)

a = [9,11,13,4,6,5,7,12,1,10,2,8,3,16,14]
SelectionSort(a)

#冒泡顺序
def BubbleSort(a):
    n = len(a)
    #   右边界     取值范围  步长

    for i in range(n-1,-1,-1):
        for j in range(0,i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
        print(a)
a = [-5,9,11,13,32,4,1,10,88,2,8,3,16,14]
BubbleSort(a)

#插入排序
def InsertionSort(a):
    n = len(a)
    for i in range(1,n):
        x = a[i] #令当前选择的数i为x
        j = i-1  #令i前面相邻的数为j
        while j >= 0:
            if x <= a[j]:
                a[j+1] = a[j]
                j -= 1
            else:
                break
            a[j+1] = x #将i插入到对应位置
            print(a)

a = [8,5,6,4,3,7,10,2]
InsertionSort(a)

#归并排序
#                  mid = start和end的中点
def Merge(a, start, mid, end):
    tmp = [] #临时列表
    l = start #两个游标l和r 分别从两端区间的起点开始
    r = mid+1
    while l <= mid and r <= end:
        if a[l] > a[r]:
            tmp.append(a[l])
            l += 1
        else:
            tmp.append(a[r])
            r += 1
    tmp.extend(a[l:mid+1]) #剩余部分塞入临时列表
    tmp.extend(a[r:end+1])
    for i in range(start,end+1):
        a[i] = tmp[i-start]  #临时列表的值拷贝回原列表a
 #以上完成了一次合并

def MergeSort(a,start,end): #递归函数
    if start == end:
        return
    mid = (start + end) // 2
    MergeSort(a, start, mid)
    MergeSort(a, mid+1, end)
    Merge(a, start, mid, end)

a = [101,11,13,51,7,12,1,8,10,2,17,3,16,14]
MergeSort(a,0,13)

#桶排序
def SelectionSort(a):
    n = len(a)
    for i in range(n-1):
        min = i
        for j in range(i+1,n):
            if (a[j] <= a[min]):
                min = j
        a[i], a[min] = a[min], a[i]

def BucketSort(a):
    minV = min(a)
    maxV = max(a)
    bucketCount = 3
    bucket = [ [],[],[]]
    perBucket = (maxV - minV + bucketCount) // bucketCount
       #每个桶不同数字的元素个数

    for num in a:
        bucketIndex = (num - minV) // perBucket
        bucket[bucketIndex].append(num)

    for i in range(bucketCount):
        SelectionSort(bucket[1])

    idx = 0
    for i in range(bucketCount):
        for v in bucket[i]:
            a[idx] = v
            idx += 1
    print(bucket)
    print(a)

a = [1011,23211,123423,511,724332,-1124234]
BucketSort(a)

#计数排序
def CountingSort(a):
    n = len(a)
    cntlen = max(a)+1
    cnt = [0] * cntlen
    for val in a:
        cnt[val] += 1
    print(cnt)
    n = 0
    for val in range(0, cntlen):
        while cnt[val] > 0:
            cnt[val] -= 1
            a[n] = val
            n += 1

a = [2,3,1,3,2,1,4,2,4,6,2]
CountingSort(a)
print(a)

#基数排序
def RadixSort(a):
    base = 1
    maxv = max(a)
    while base < maxv:
        bucket = []
        for idx in range(10):
            bucket.append([])
        for num in a:
            idx = num // base % 10
            bucket[idx].append(num)
        l = 0
        for idx in range(10):
            for v in bucket[idx]:
                a[l] = v
                l += 1
        print(a)
        base *= 10
a = [1,54,-45,456,765,2123,-8791,9981,100001]
RadixSort(a) #负数咋办呢

#快速排序
def QuickSortPivot(a,start,end):
    pivot = start
    j = start + 1
    for i in range(start+1,end + 1):
        if a[i] <= a[pivot]:
            a[i],a[j] = a[j],a[i]
            j += 1
    a[pivot],a[j-1] = a[j-1],a[pivot]
    pivot = j - 1
    print(a[pivot],a[start:pivot],a[pivot+1:end+1])
    return pivot

def QuickSort(a,start,end):
    if start >= end:
        return
    pivot = QuickSortPivot(a,start,end)
    QuickSort(a,start,pivot - 1)
    QuickSort(a,pivot + 1,end)

a = [8,5,12,6,4,3,7,9,2,1,10,11]
QuickSort(a,0,11)
print(a)

#随机快速排序
import random

def QuickSortPivot(a,start,end):
    randIdex = random.randint(start,end)
    a[start],a[randIdex] = a[randIdex],a[start]
    pivot = start
    j = start + 1
    for i in range(start+1,end + 1):
        if a[i] <= a[pivot]:
            a[i],a[j] = a[j],a[i]
            j += 1
    a[pivot],a[j-1] = a[j-1],a[pivot]
    pivot = j - 1
    print(a[pivot],a[start:pivot],a[pivot+1:end+1])
    return pivot

def QuickSort(a,start,end):
    if start >= end:
        return
    pivot = QuickSortPivot(a,start,end)
    QuickSort(a,start,pivot - 1)
    QuickSort(a,pivot + 1,end)

a = [8,5,12,6,4,3,7,9,2,1,10,11]
QuickSort(a,0,11)
print(a)

def ShellSort(a):
    n = len(a)
    gap = n // 2
    while gap > 0:
        for i in range(gap,n):
            x = a[i]
            j = i
            while j >= gap:
                if x < a[j-gap]:
                    a[j] = a[j-gap]
                else:
                    break
                j -= gap
            a[j] = x
        print(a)
        gap = gap // 2

a = [8,5,6,4,3,7,10,2]
ShellSort(a)

#堆排序
def maxHeaoify(heap,start,end):
    son = start * 2
    while son <= end:
        if son + 1 <= end and heap[son + 1] > heap[son]:
            son += 1
        if heap[son] > heap[start]:
            heap[start], heap[son] = heap[son], heap[start]
            start, son = son, son * 2
        else:
            break

def HeapSort(a):
    heap = [None] + a
    root = 1
    l = len(heap)
    for i in range(l//2,root-1,-1):
        maxHeaoify(heap,i,l-1)
    for i in range(l-1,root,-1):
            heap[i],heap[root] = heap[root],heap[i]
            maxHeaoify(heap,root,i-1)
    return heap[root:]

a = [9,11,13,4,6,5,7,12,1,10,2,8,3,16,14]
print(HeapSort(a))
